"""1.分治法解决金块问题，即找最大最小。延伸思考：分治法解决找次大元素、第K大元素。"""
def find_min_max(arr, left, right):
    """
    分治法解决金块问题：同时找到最大值和最小值
    """
    # 基本情况：只有一个元素
    if left == right:
        return arr[left], arr[left]

    # 基本情况：只有两个元素
    if right - left == 1:
        return (arr[left], arr[right]) if arr[left] < arr[right] else (arr[right], arr[left])

    # 分治：将数组分成两半
    mid = (left + right) // 2
    min1, max1 = find_min_max(arr, left, mid)
    min2, max2 = find_min_max(arr, mid + 1, right)

    # 合并结果
    overall_min = min(min1, min2)
    overall_max = max(max1, max2)

    return overall_min, overall_max


def find_second_largest(arr):
    """
    分治法找次大元素
    """

    def _find_max_and_second(arr, left, right):
        if left == right:
            return arr[left], float('-inf')

        if right - left == 1:
            if arr[left] > arr[right]:
                return arr[left], arr[right]
            else:
                return arr[right], arr[left]

        mid = (left + right) // 2
        max1, second1 = _find_max_and_second(arr, left, mid)
        max2, second2 = _find_max_and_second(arr, mid + 1, right)

        if max1 > max2:
            return max1, max(second1, max2)
        else:
            return max2, max(second2, max1)

    return _find_max_and_second(arr, 0, len(arr) - 1)[1]


def find_kth_largest(arr, k):
    """
    分治法找第K大元素（基于快速选择算法）
    """
    import random

    def _quick_select(arr, left, right, k):
        if left == right:
            return arr[left]

        # 随机选择基准
        pivot_idx = random.randint(left, right)
        arr[pivot_idx], arr[right] = arr[right], arr[pivot_idx]

        # 分区操作
        pivot = arr[right]
        i = left
        for j in range(left, right):
            if arr[j] >= pivot:  # 注意：找第k大，所以用>=
                arr[i], arr[j] = arr[j], arr[i]
                i += 1
        arr[i], arr[right] = arr[right], arr[i]

        # 判断基准的位置
        if i - left == k - 1:
            return arr[i]
        elif i - left > k - 1:
            return _quick_select(arr, left, i - 1, k)
        else:
            return _quick_select(arr, i + 1, right, k - (i - left + 1))

    return _quick_select(arr.copy(), 0, len(arr) - 1, k)


# 测试金块问题
print("=== 金块问题测试 ===")
arr = [3, 7, 2, 9, 1, 8, 5, 6]
min_val, max_val = find_min_max(arr, 0, len(arr) - 1)
print(f"数组: {arr}")
print(f"最小值: {min_val}, 最大值: {max_val}")
print(f"次大元素: {find_second_largest(arr)}")
print(f"第3大元素: {find_kth_largest(arr, 3)}")
print()